package com.laotang.第_15_章_图论算法.图的DFS和BFS;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Graph_DFS {

    // 树的前序遍历
    class TreeNode {
        int val;
        List<TreeNode> children;

        TreeNode(int val) {
            this.val = val;
            this.children = new ArrayList<>();
        }
    }

    public void dfs(TreeNode root) {
        if (root == null) return;

        System.out.println(root.val);

        for (TreeNode child : root.children) {
            dfs(child);
        }
    }

    // 图的深度优先遍历
    class Node {
        int val;
        List<Node> neighbors;

        Node(int val) {
            this.val = val;
            this.neighbors = new ArrayList<>();
        }
    }

    Set<Node> visited = new HashSet<>();
    public void dfs(Node node) {
        if (node == null) return;

        System.out.println(node.val);
        visited.add(node);

        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) dfs(neighbor);
        }
    }
}
